package com.yoshino.leetcode.improve40.Threetysecond;

class Solution {
    public int minCut(String s) {
        // 得到子串回文字段 + 遍历
        int n = s.length();
        if (n == 1) {
            return 0;
        }
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 右边界
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (i - j < 3) {
                    dp[j][i] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[j][i] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
                }
            }
        }
        // 0 到 n - 1 的最少分割次数
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            // i 为右边界
            if (!dp[0][i]) {
                // 整个非回文串
                // 最多分割次数
                res[i] = i;
                for (int j = 1; j <= i; j++) {
                    // 从左边界找回文串
                    if (dp[j][i]) {
                        res[i] = Math.min(res[i], res[j - 1] + 1);
                    }
                }
            }
        }
        return res[n - 1];
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int n1= s1.length(), n2 = s2.length(), n3 = s3.length();
        if (n1 + n2 != n3) {
            return false;
        }
        boolean[][] f = new boolean[n1 + 1][n2 + 1];
        f[0][0] = true;
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                int ind = i + j - 1;
                if (i > 0) {
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(ind));
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(ind));
                }
            }
        }
        return f[n1][n2];
    }
}